home *** CD-ROM | disk | FTP | other *** search
/ CD School House 9 / CD School House 9.0 - Wayzata Technology (1994).iso / pc / dos / math / fsultra1 / ultra.doc < prev    next >
Text File  |  1992-06-18  |  11KB  |  261 lines
  1. FSU - ULTRA    The greatest random number generator that ever was
  2.         or ever will be.  Way beyond Super-Duper.
  3.         (Just kidding, but we think its a good one.)
  4.  
  5. Authors:    Arif Zaman (arif@stat.fsu.edu) and
  6.         George Marsaglia (geo@stat.fsu.edu).
  7.  
  8. Date:        27 May 1992
  9.  
  10. Version:    1.05
  11.  
  12. Copyright:    To obtain permission to incorporate this program into
  13.         any commercial product, please contact the authors at
  14.         the e-mail address given above or at
  15.  
  16.         Department of Statistics and
  17.         Supercomputer Computations Research Institute
  18.         Florida State University
  19.         Tallahassee, FL 32306.
  20.  
  21. See Also:    README        for a brief description
  22.         ULTRA.DOC    for a detailed description
  23.  
  24. -----------------------------------------------------------------------
  25.  
  26. DETAILED DESCRIPTION:
  27.  
  28.   This is an implementation (in C and in PC assembler) of a random number
  29.   generator with many good properties that common generators lack, namely:
  30.  
  31.  
  32.   HIGH QUALITY
  33.  
  34.       o  Extremely long period (more than 10^356---that's more than
  35.      10^270 numbers for each atom in the universe, in case you
  36.       want to simulate creation).
  37.  
  38.       o  Combines two different types of generators, to achieve a very
  39.      thorough mixing.
  40.  
  41.       o  All possible values of 37 consecutive numbers occur with the
  42.      correct frequencies in the long run.
  43.  
  44.       o  Single precision reals (by far the most common) are guaranteed
  45.      to have full precision in the fraction (mantissa).
  46.      Almost all generators  produce reals by dividing a 32 (or 31) bit
  47.      integer by 2^32 (2^31).  This means the smallest possible
  48.      random reals are small multiples of 2^(-32).  This implementation
  49.      will produce random reals down to 2^(-64) with the proper
  50.      frequencies.  This makes it impossible to get a 0, which
  51.      avoids the rare, but irritating program-stopping situation
  52.      that arises from taking a logarithm of, or dividing by, zero.
  53.  
  54.   VERSATILE
  55.  
  56.       o  Random bits, bytes, 16 or 32 bit integers with or without sign.
  57.  
  58.       o  Single or double precision real numbers signed or unsigned.
  59.  
  60.   FAST
  61.  
  62.       o  We have aimed first for quality, and have sacrificed speed for
  63.      quality at every step. This can be seen in the implementation
  64.      of the single precision uni or vni, or in the intrand routines.
  65.  
  66.       o  Despite this, the speed of this method is only slightly slower
  67.      than an efficient implementation of the most common simple
  68.      congruential generator, and is faster than some implementations.
  69.  
  70.       o  The Subtract-with-Borrow (SWB) operation is part of almost
  71.      every machine architecture, but is not available to most high 
  72.      level languages. Using assembler, the entire SWB operation 
  73.      can be done in a single instrution.
  74.  
  75.       o  For those who are interested in pure speed, a FAST option
  76.      is available. This skips the mixing with a congruential
  77.      generator, providing just a simple SWB sequence. The period
  78.      is still extremely long, and the randomness properties should
  79.      satisfy all but the most demanding users.
  80.  
  81.       o  For those with 80386 or 80486 hardware which allows for 32-bit
  82.      multiplications, some 30% speedup is available by using the
  83.      32-bit versions, which exploit these instructions.
  84.  
  85.       o  Sample timings using Turbo-C++ 1.0 (small memory model) in 
  86.      microseconds on a Gateway 486/33C PC were:
  87.  
  88.     Full version (SWB+congruential)
  89.         dvni  duni   vni   uni 32bit 31bit 16bit 15bit  8bit  7bit  1bit
  90.     32bit   7.51  7.66  5.28  5.30  3.18  3.25  1.91  1.91  1.39  1.39  1.46
  91.     plain  10.65 10.80  6.93  6.90  4.65  4.68  2.75  2.72  1.74  1.74  1.50
  92.     C      18.50 18.67  9.68  9.78  8.07  8.16  4.89  4.86  2.86  2.86  2.78
  93.  
  94.     `FAST' version (no congruential)
  95.         dvni  duni   vni   uni 32bit 31bit 16bit 15bit  8bit  7bit  1bit
  96.     32bit   4.82  5.03  3.88  3.84  1.82  1.76  1.23  1.23  1.07  1.07  1.47
  97.     plain   5.92  6.05  4.49  4.42  2.26  2.28  1.60  1.54  1.23  1.16  1.43
  98.     C      11.49 11.63  6.28  6.29  4.52  4.64  3.10  3.13  1.93  1.93  2.73
  99.  
  100.        Timings (in microseconds) were obtained by timing a long loop,
  101.        hence they include the subroutine calling and looping times.
  102.  
  103.        32bit - refers to the 80386/80486 ('X' version).
  104.        plain - is the plain assembler implementation.
  105.        C     - is the ULTRA.C (entirely in Turbo C) implementation.
  106.  
  107.   PORTABLE
  108.  
  109.       o  The entire generator is based around a random stream of 32bit
  110.      words, which can be generated a byte at a time (or even a bit
  111.      at a time). Since this same bit stream will be duplicated on any
  112.      architechture, the entire sequence of random numbers will be
  113.      the same, even for different architectures.         
  114.  
  115.       o  Actually the outputs of i16bit, i15bit, i8bit, i7bit and i1bit
  116.      may be different depending on whether the machine is `big-endian'
  117.      or `little-endian'. On the other hand, the i32bit and i31bit
  118.      as well as uni, vni, duni and dvni should not be affected by
  119.      this. Even they byte routines could be made identical at the
  120.      cost of performance.
  121.  
  122.       o  It is essential to implement the algorithm in assembler in order
  123.      to gain its tremendous speed advantages. On the other hand
  124.      a C program (ultra.c) which is about half as fast as the assembler
  125.      has been provided to to aid understanding and debugging the
  126.      implementation on another machine.
  127.  
  128.       o  We would welcome any news about successful ports to other
  129.      architectures. To begin a port, first examine ultra.c. If
  130.      you understand PC assembler, it would also help to look at
  131.      ult32cod.asm.
  132.  
  133.  
  134.   The principal component of ULTRA is the Subtract-with-Borrow (SWB)
  135.   generator that is described in our paper `A New Class of Random Number
  136.   Generators', Annals of Applied Probability V1 462-480, 1991.
  137.   We use a 148 byte seed array, to obtain an astronomically large
  138.   period, while satisfying all the usual theoretical and experimental
  139.   tests for randomness.
  140.  
  141.   The other component of ULTRA is the congruential generator with
  142.   multiplier 69069 and base 2^32. This is a very well known, reliable
  143.   (but short period) generator, tried and tested. It is, for example,
  144.   the generator built into VAX's. 
  145.  
  146.   The results of both of these generators are xor'ed to provide the
  147.   bytes which form the output of the ULTRA random number generator.
  148.  
  149. ---------------------------------------------------------------------
  150. COMPILATION INSTRUCTIONS
  151.  
  152.   This assembler code is written for TASM 2.0, to allow one program
  153.   to serve for many different languages.
  154.  
  155.   The header files define language dependent macros. These are:
  156.   ULTRA_C.ASM, ULTRA_TP.ASM and ULTRA_LH.ASM are for Turbo C, 
  157.   Turbo Pascal and Lahey Fortran respectively.
  158.  
  159.   All of these files then include the core files ULTRADAT.INC and
  160.   ULTRACOD.INC, which actually implement the algorithm.
  161.  
  162.   A second set of files ULT32_C.ASM, ULT32_TP.ASM, and ULT32_LH.ASM
  163.   which include ULTRADAT.INC and ULT32COD.INC are the same programs
  164.   rewritten to use 32 bit code available on 80386 or 80486 machines
  165.   for faster execution.
  166.  
  167.   The C files ULTRA_C.ASM and ULT32_C.ASM depend on the user defining
  168.   a variable `m' to be the memory model. Thus the command:
  169.  
  170.     TASM -dm=small ULTRA_C.ASM
  171.  
  172.   will create a small memory model object file. The memory model can
  173.   be any of `tiny', `small', `compact', `medium', `large' or `huge'.
  174.  
  175.   Implementation in any other language which is not supported here
  176.   is simply a matter of fixing the header file.
  177.  
  178. ----------------------------------------------------------------------
  179. FUNCTIONS and SUBROUTINES
  180.  
  181.   The i[n]bit functions
  182.   ---------------------
  183.  
  184.     i1bit, i7bit, i8bit, i15bit, i16bit, i31bit, i32bit
  185.  
  186.     For n=32, 16, 8 these return a 4, 2, 1 byte answer which has
  187.     all bits random, hence is a random integer. If it is treated
  188.     as a signed integer, it ranges from -2^(n-1) to 2^(n-1)-1.
  189.     As an unsigned integer it range is 0 to 2^n-1.
  190.  
  191.     For n=31, 15, 7 these return a 4, 2, 1 byte answer, but since
  192.     the sign bit is always off, these are always positive integers
  193.     from 0 and 2^n-1.
  194.  
  195.   [d][u/v]ni functions
  196.   --------------------
  197.  
  198.     uni() is a single precision uniform random number strictly
  199.      between 0 and 1.  uni() always has 24 bits of precision;
  200.      it will never be 0 (or 1).
  201.  
  202.     vni() is a single precision uniform between -1 and 1. It always has
  203.       24 bits of precision, and it never takes on the extreme values.
  204.  
  205.     duni() and dvni() are double precision version of uni and vni.
  206.       They have no more than 64 bits of precision.
  207.  
  208.   rinit(n1,n2)
  209.   ------------
  210.  
  211.     Calling rinit(n1,n2) initializes the seed array, using
  212.     the two 32-bit integer arguments n1 and n2.
  213.     The first argument should be odd (if it isn't it is made so).
  214.     If rinit is not called, the built-in default state is
  215.     what would result from the call rinit(1234567,7654321).
  216.  
  217.   swbstate and swbsize
  218.   --------------------
  219.  
  220.     In order to allow the user to save the state of the generator
  221.     so that it could take up from where it left off, the global variable
  222.     swbstate is an array containing swbsize bytes. Saving the entire
  223.     array will save the state of the generator. The eight bytes
  224.     following this array are insensitive to being changed, so if
  225.     a few more bytes are restored because the language only allows
  226.     integer arrays, there should be no problem. Thus you can always
  227.     save/restore 4 + 4*(swbsize div 4) bytes, if you need to.
  228.     Currently swbsize is 653 bytes.
  229.  
  230. ----------------------------------------------------------------------
  231. ADDING ANOTHER LANGUAGE
  232.  
  233.   The Header files are where all language-dependent entry and exit
  234.   conventions have been placed. If you want to add another language
  235.   which uses another protocol to pass arguments, return values, or
  236.   save registers, this is where you want to modify the program.
  237.  
  238.   You must define:
  239.       EnterProcedure:
  240.         Save registers etc.
  241.         Make DS point to the data segement if it doesn't.
  242.       ExitProcedure:
  243.         Restore registers and execute a ret.
  244.       Enter2arg:
  245.         Save registers etc.
  246.         Make ES and DS point to the data segment.
  247.     in Ultra:  Load the two arguments for RINIT into CONGX and SHRGX.
  248.     in Ult32:  Load the two arguments into EAX and EBX.
  249.       Exit2arg: Restore registers and execute a ret.
  250.  
  251.       DwordFn           The function result is in DX:AX. Place it
  252.             where the language expects it to be.
  253.       WordFn            Put result from AX to where it is expected.
  254.       ByteFn            Put result from AL to where it is expected.
  255.       RealFn,DoubleFn   Put result from NDP stack to where it should be.
  256.  
  257.   The segment names, classes etc must also be defined here.
  258.   the files ULTRADAT.INC and ULTRACOD.INC (or ULT32DAT.INC
  259.   and ULT32COD.INC) must be included in the appropriate
  260.   segments. Look at examples of header files for more information.
  261.